home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / network / admin / xinetd.2 / xinetd / xinetd.2.1.7-linux.4 / libs / src / pq / hpq.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-09-10  |  5.5 KB  |  251 lines
  1. /*
  2.  * (c) Copyright 1993 by Panagiotis Tsirigotis
  3.  * All rights reserved.  The file named COPYRIGHT specifies the terms 
  4.  * and conditions for redistribution.
  5.  */
  6.  
  7. static char RCSid[] = "$Id: hpq.c,v 1.5 1995/09/10 18:33:46 chuck Exp $" ;
  8. static char version[] = VERSION ;
  9.  
  10. #include <sys/param.h>
  11. #include "pq.h"
  12. #include "hpqimpl.h"
  13.  
  14. #define PRIVATE            static
  15.  
  16. #ifndef NULL
  17. #define NULL 0
  18. #endif
  19.  
  20. #define PARENT( i )        ( i >> 1 )
  21. #define LEFT( i )            ( i << 1 )
  22. #define RIGHT( i )        ( LEFT( i ) + 1 )
  23.  
  24. int pq_errno ;
  25.  
  26. #define INITIAL_ARRAY_SIZE                100                /* entries */
  27.  
  28. #if defined(linux) || defined(BSD)
  29. PRIVATE int grow( header_s *hp ) ;
  30. PRIVATE void restore_heap( register header_s *hp , unsigned start ) ;
  31. #endif
  32.  
  33. pq_h __hpq_create( func, flags, errnop )
  34.     int (*func)() ;
  35.     int flags ;
  36.     int *errnop ;
  37. {
  38.     register header_s *hp ;
  39.     int *errp = ( errnop == NULL ) ? &pq_errno : errnop ;
  40.     char *malloc() ;
  41.  
  42.     /*
  43.      * Check if the user has provided the necessary comparison functions
  44.      */
  45.     if ( func == NULL )
  46.         HANDLE_ERROR( flags, NULL, errp, PQ_ENOFUNC,
  47.                 "HPQ __hpq_create: missing object-object comparator\n" ) ;
  48.  
  49.     hp = HHP( malloc( sizeof( header_s ) ) ) ;
  50.     if ( hp == NULL )
  51.         HANDLE_ERROR( flags, NULL, errp, PQ_ENOMEM,
  52.                                                 "HPQ __hpq_create: malloc failed\n" ) ;
  53.     
  54.     /*
  55.      * Allocate object array
  56.      */
  57.     hp->objects = (pq_obj *) malloc( INITIAL_ARRAY_SIZE * sizeof( pq_obj ) ) ;
  58.     if ( hp->objects == NULL )
  59.     {
  60.         free( (char *)hp ) ;
  61.         HANDLE_ERROR( flags, NULL, errp, PQ_ENOMEM, 
  62.                                                 "HPQ __hpq_create: malloc failed\n" ) ;
  63.     }
  64.  
  65.     /*
  66.      * Initialize the header
  67.      */
  68.     hp->is_better = func ;
  69.     hp->errnop = errp ;
  70.     hp->flags = flags ;
  71.     hp->max_size = INITIAL_ARRAY_SIZE ;
  72.     hp->cur_size = 0 ;
  73.     return( (pq_h) hp ) ;
  74. }
  75.  
  76.  
  77. void __hpq_destroy( handle )
  78.     pq_h handle ;
  79. {
  80.     header_s *hp = HHP( handle ) ;
  81.  
  82.     free( (char *) hp->objects ) ;
  83.     free( (char *)hp ) ;
  84. }
  85.  
  86.  
  87. int __hpq_insert( handle, object )
  88.     pq_h handle ;
  89.     pq_obj object ;
  90. {
  91.     register header_s *hp = HHP( handle ) ;
  92.     register unsigned i, parent ;
  93.  
  94.     if ( object == NULL )
  95.         HANDLE_ERROR( hp->flags, PQ_ERR, hp->errnop, PQ_ENULLOBJECT,
  96.                                             "HPQ __hpq_insert: NULL object\n" ) ;
  97.  
  98.     /*
  99.      * Make sure there is room to store the object
  100.      */
  101.     if ( hp->cur_size >= hp->max_size && grow( hp ) == PQ_ERR )
  102.         return( PQ_ERR ) ;
  103.  
  104.     i = hp->cur_size++ ;
  105.     parent = PARENT( i ) ;
  106.     while ( i > 0 && (*hp->is_better)( object, hp->objects[ parent ] ) )
  107.     {
  108.         hp->objects[ i ] = hp->objects[ parent ] ;
  109.         i = parent ;
  110.         parent = PARENT( i ) ;
  111.     }
  112.     hp->objects[ i ] = object ;
  113.     return( PQ_OK ) ;
  114. }
  115.  
  116.  
  117. #define CUTOFF                                (INITIAL_ARRAY_SIZE * 128)
  118. #define INCREMENT                            CUTOFF
  119.  
  120. /*
  121.  * Grow the table.
  122.  * Algorithm:
  123.  *            while the table_size is less than CUTOFF, double the size.
  124.  *         if it grows greater than CUTOFF, increase the size by INCREMENT
  125.  *            (these number are in entries, not bytes)
  126.  */
  127. PRIVATE int grow( hp )
  128.     header_s *hp ;
  129. {
  130.     unsigned new_size ;
  131.     char *new_objects ;
  132.     char *realloc() ;
  133.  
  134.     if ( hp->max_size < CUTOFF )
  135.         new_size = hp->max_size * 2 ;
  136.     else
  137.         new_size = hp->max_size + INCREMENT ;
  138.  
  139.     new_objects = realloc( (char *)hp->objects, new_size * sizeof( pq_obj ) ) ;
  140.     if ( new_objects == NULL )
  141.         HANDLE_ERROR( hp->flags, PQ_ERR, hp->errnop, PQ_ENOMEM,
  142.                                         "HPQ grow: out of memory\n" ) ;
  143.     
  144.     hp->max_size = new_size ;
  145.     hp->objects = (pq_obj *) new_objects ;
  146.     return( PQ_OK ) ;
  147. }
  148.  
  149.  
  150. pq_obj __hpq_extract_head( handle )
  151.     pq_h handle ;
  152. {
  153.     register header_s *hp = HHP( handle ) ;
  154.     pq_obj object ;
  155.     void restore_heap() ;
  156.  
  157.     if ( hp->cur_size == 0 )
  158.         return( NULL ) ;
  159.     
  160.     object = hp->objects[ 0 ] ;
  161.     hp->objects[ 0 ] = hp->objects[ --hp->cur_size ] ;
  162.     restore_heap( hp, 0 ) ;
  163.     return( object ) ;
  164. }
  165.  
  166.  
  167. #define EXISTS( hp, i )                ( i < hp->cur_size )
  168. #define IS_BETTER( hp, i, j )        \
  169.             ( (*hp->is_better)( hp->objects[ i ], hp->objects[ j ] ) )
  170. #define SWAP( hp, i, j )                                \
  171.         {                                                        \
  172.             pq_obj t = hp->objects[ i ] ;                \
  173.             hp->objects[ i ] = hp->objects[ j ] ;    \
  174.             hp->objects[ j ] = t ;                        \
  175.         }
  176.  
  177. PRIVATE void restore_heap( hp, start )
  178.     register header_s *hp ;
  179.     unsigned start ;
  180. {
  181.     register unsigned current = start ;
  182.     register unsigned better = current ;
  183.  
  184.     for ( ;; )
  185.     {
  186.         register unsigned left = LEFT( current ) ;
  187.         register unsigned right = RIGHT( current ) ;
  188.  
  189.         /*
  190.          * Meaning of variables:
  191.          *
  192.          *        current:        the current tree node
  193.          *        left:            its left child
  194.          *        right:        its right child
  195.          *        better:         the best of current,left,right
  196.          *
  197.          * We start the loop with better == current
  198.          *
  199.          * The code takes advantage of the fact that the existence of
  200.          * the right child implies the existence of the left child.
  201.          * It works by finding the better of the two children (and puts
  202.          * that in better) and comparing that against current.
  203.          */
  204.         if ( EXISTS( hp, right ) )
  205.             better = IS_BETTER( hp, left, right ) ? left : right ;
  206.         else if ( EXISTS( hp, left ) )
  207.             better = left ;
  208.  
  209.         if ( better == current || IS_BETTER( hp, current, better ) )
  210.             break ;
  211.         else 
  212.         {
  213.             SWAP( hp, current, better ) ;
  214.             current = better ;
  215.         }
  216.     }
  217. }
  218.  
  219.  
  220. int __hpq_delete( handle, object )
  221.     pq_h handle ;
  222.     register pq_obj object ;
  223. {
  224.     register header_s *hp = HHP( handle ) ;
  225.     register unsigned i ;
  226.  
  227.     if ( object == NULL )
  228.         HANDLE_ERROR( hp->flags, PQ_ERR, hp->errnop, PQ_ENULLOBJECT,
  229.                                             "HPQ __hpq_delete: NULL object\n" ) ;
  230.  
  231.     /*
  232.      * First find it
  233.      */
  234.     for ( i = 0 ;; i++ )
  235.     {
  236.         if ( i < hp->cur_size )
  237.             if ( object == hp->objects[ i ] )
  238.                 break ;
  239.             else
  240.                 continue ;
  241.         else
  242.             HANDLE_ERROR( hp->flags, PQ_ERR, hp->errnop, PQ_ENOTFOUND,
  243.                     "HPQ __hpq_delete: object not found\n" ) ;
  244.     }
  245.  
  246.     hp->objects[ i ] = hp->objects[ --hp->cur_size ] ;
  247.     restore_heap( hp, i ) ;
  248.     return( PQ_OK ) ;
  249. }
  250.  
  251.